#define _CRT_SECURE_NO_WARNINGS 1
class Solution {
public:
    int ret = 0;
    bool bp[16];
    int countArrangement(int n) {
        dfs(n, 0, 1);
        return ret;
    }
    void dfs(int n, int s, int pos)
    {
        if (n == s)
        {
            ret++;
            return;
        }

        for (int i = 1; i <= n; i++)
        {
            if ((i % pos == 0 || pos % i == 0) && bp[i] == false)
            {
                bp[i] = true;
                dfs(n, s + 1, pos + 1);
                bp[i] = false;
            }
        }
    }
};